package com.itheima.algorithm.binarysearchtree;

import com.itheima.algorithm.binarytree.TreeNode;

/**
 * @author: TylerZhong
 * @description:
 */
public class E06Leetcode1008 {
/*    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 1; i < preorder.length; i++) {
            insert(root, preorder[i]);
        }
        return root;
    }*/

    /*private TreeNode insert(TreeNode node, int pre) {
        if (node == null) {
            return new TreeNode(pre);
        }
        if (pre < node.val) {
            node.left = insert(node.left, pre);
        } else {
            node.right = insert(node.right, pre);
        }
        return node;
    }*/

/*    int i = 0;
    private TreeNode insert(int[] preorder, int max) {
        if (i == preorder.length) {
            return null;
        }
        int val = preorder[i];
        if (val > max) {
            return null;
        }
        TreeNode node = new TreeNode(val);
        i++;
        node.left = insert(preorder, val);
        node.right = insert(preorder, max);
        return node;
    }*/

    public TreeNode bstFromPreorder(int[] preorder) {
        return partion(preorder, 0, preorder.length-1);
    }

    public TreeNode partion(int[] preorder, int start, int end) {
        if (start > end) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[start]);
        int index = start+1;
        while (index <= end) {
            if (preorder[index] > preorder[start]) {
                break;
            }
            index++;
        }
        // index 就是右子树的起点
        node.left = partion(preorder, start + 1, index - 1);
        node.right = partion(preorder, index, end);
        return node;
    }
}
